#include <bits/stdc++.h>

using namespace std;

// 戳气球
// 有 n 个气球，编号为0到n-1，每个气球上都标有一个数字，这些数字存在数组nums中
// 现在要求你戳破所有的气球。戳破第 i 个气球
// 你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币
// 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号
// 如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球
// 求所能获得硬币的最大数量
// 测试链接 : https://leetcode.cn/problems/burst-balloons/

class Solution 
{
public:
    // 记忆化搜索
    int maxCoins1(vector<int>& nums) 
    {
        int n = nums.size();
        // a b c d e
		// 1 a b c d e 1
        int val[n + 2];
        val[0] = val[n + 1] = 1;
        for(int i = 1; i <= n; ++i) val[i] = nums[i - 1];
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, -1));
        return f1(val, 1, n, dp);
    }

	// arr[l...r]这些气球决定一个顺序，获得最大得分返回！
	// 一定有 : arr[l-1]一定没爆！
	// 一定有 : arr[r+1]一定没爆！
	// 尝试每个气球最后打爆
    int f1(int* val, int l, int r, vector<vector<int>>& dp)
    {
        if(dp[l][r] != -1) return dp[l][r];
        int ans;
        if(l == r) ans = val[l - 1] * val[l] * val[r + 1];
        else
        {
            // l   ....r
			// l +1 +2 .. r
            ans = max(
                val[l - 1] * val[l] * val[r + 1] + f1(val, l + 1, r, dp),  // l位置的气球最后打爆
                val[l - 1] * val[r] * val[r + 1] + f1(val, l, r - 1, dp)); // r位置的气球最后打爆
            for(int k = l + 1; k < r; ++k)
            {
                // k位置的气球最后打爆
				// l...k-1  k  k+1...r
                ans = max(ans, val[l - 1] * val[k] * val[r + 1] + f1(val, l, k - 1, dp) + f1(val, k + 1, r, dp));
            }
        }
        dp[l][r] = ans;
        return ans;
    }

    // 严格位置依赖的动态规划
    int maxCoins2(vector<int>& nums) 
    {
        int n = nums.size();
        int val[n + 2];
        val[0] = val[n + 1] = 1;
        for(int i = 1; i <= n; ++i) val[i] = nums[i - 1];
            
        int dp[n + 1][n + 1];
        memset(dp, 0, sizeof dp);
        for(int i = 1; i <= n; ++i) dp[i][i] = val[i - 1] * val[i] * val[i + 1];
        for(int l = n - 1; l >= 1; --l)
        {
            for(int r = l + 1; r <= n; ++r)
            {
                dp[l][r] = max(
                    val[l - 1] * val[l] * val[r + 1] + dp[l + 1][r],  // l位置的气球最后打爆
                    val[l - 1] * val[r] * val[r + 1] + dp[l][r - 1]); // r位置的气球最后打爆
                for(int k = l + 1; k < r; ++k)
                {
                    // k位置的气球最后打爆
				    // l...k-1  k  k+1...r
                    dp[l][r] = max(dp[l][r], val[l - 1] * val[k] * val[r + 1] + dp[l][k - 1] + dp[k + 1][r]);
                }
            }
        }
        return dp[1][n];
    }
};